package com.yequan.leetcode.linkedlist.reverseBetween_92;

import com.yequan.leetcode.linkedlist.ListNode;

/**
 * @author yequan
 * @date 2022/03/03 08:19
 **/
public class ReverseBetween {

    public ListNode reverseBetween1(ListNode head, int left, int right) {
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode preNode = preHead;
        //1.找出待反转链表开始的位置
        for (int i = 0; i < left - 1; i++) {
            preNode = preNode.next;
        }
        ListNode rightNode = preNode;
        //2.找出待反转链表结束的位置
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        //截取的新链表的位置,同时也是反转链表的结束位置
        ListNode leftNode = preNode.next;
        //右侧链表开始的位置,合并链表的位置
        ListNode currNode = rightNode.next;

        preNode.next = null;
        rightNode.next = null;

        ListNode reversedNode = reverse1(leftNode);

        //合并链表
        preNode.next = reversedNode;
        //反转之后的链表尾部接上右侧的子链表
        leftNode.next = currNode;
        return preHead.next;
    }

    public ListNode reverseBetween2(ListNode head, int left, int right) {
        ListNode preHead = new ListNode(-1);
        preHead.next = head;
        ListNode preNode = preHead;
        //找出需要反转子链表的头节点的位置
        for (int i = 0; i < left - 1; i++) {
            preNode = preNode.next;
        }
        //找出需要反转子链表右侧的子链表的位置
        ListNode rightNode = preNode;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }
        //反转链表前进行现场保存
        ListNode leftNode = preNode.next;
        ListNode subRightNode = rightNode.next;

        //断链
        preNode.next = null;
        rightNode.next = null;

        //反转子链
        ListNode reverseNode = reverse2(leftNode);

        //合并子链:反转之后需要注意头尾
        preNode.next = reverseNode;
        leftNode.next = subRightNode;
        return preHead.next;
    }

    private ListNode reverse1(ListNode head) {
        ListNode pre = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        return pre;
    }

    private ListNode reverse2(ListNode head) {
        ListNode preNode = null;
        ListNode currentNode = head;
        while (currentNode != null) {
            ListNode nextNode = currentNode.next;
            currentNode.next = preNode;
            preNode = currentNode;
            currentNode = nextNode;
        }
        return preNode;
    }
}
